from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        sum=0;max=nums[0]
        for i in range(len(nums)):
            if sum<0:
                sum=nums[i]
            else:
                sum=sum+nums[i]
            if max<sum:
                max=sum
        return max

if __name__ == '__main__':
    s=Solution()
    list=[-2,1,-3,4,-1,2,1,-5,4]
    print(s.maxSubArray(list))